package com.leetcode.No0005;

/**
 * @program: leetcode
 * @description:
 * @author: wangzhihua
 * @date: 2021-05-28
 */
public class Solution01 {

	public String longestPalindrome(String s) {
		int[][] dp = new int[s.length()][s.length()];
		int maxLen = 1;
		int start = 0;
		int end = 0;

		for (int j = 0; j < s.length(); ++j) {
			for (int i = 0; i + j < s.length(); ++i) {
				if (s.charAt(i) == s.charAt(i + j)) {
					if (j == 0) {
						dp[i][i] = 1;
					} else {
						if (j == 1) {
							dp[i][i + 1] = 2;
						} else if (dp[i + 1][i + j - 1] > 0) {
							dp[i][i + j] = dp[i + 1][i + j - 1] + 2;
						} else {
							continue;
						}
						if (maxLen < j + 1) {
							maxLen = j + 1;
							start = i;
							end = i + j;
						}
					}
				}
			}
		}

		return s.substring(start, end + 1);
	}

}
